#include "LinkTree.h"
#include <iostream>

TreeNode::TreeNode(const ElementType &element)
{
    data = element;
    parent = nextSbling = firstChild = nullptr; // 全部置空
}

void TreeNode::Connect(TreeNode *parent) // 注意传递的参数是双亲
{
    if (!parent) // 判断如果给定的双亲是空的
        return;
    this->parent = parent;                 // this指针,因为是当前结点绑上去
    this->nextSbling = parent->firstChild; // 对顺序不敏感：使用头插，O(1)，效率比尾插(O(n))高
    parent->firstChild = this;
}

void TreeNode::Disconnect(TreeNode *parent)
{
    if (parent == nullptr && this->parent != parent) // 为空或者与我不是一个双亲
        return;
    TreeNode *travelPoint = parent->firstChild; // 遍历指针
    if (this == parent->firstChild)             // 我是双亲的第一个孩子
        parent->firstChild = this->nextSbling;  // 直接解绑   // 而且注意：右边是常量，左边是变量，不要写反了
    else
    {
        while (travelPoint->nextSbling != nullptr)
        {
            if (travelPoint->nextSbling == this)
            {
                travelPoint->nextSbling = this->nextSbling;
                break;
            }
            travelPoint = travelPoint->nextSbling;
        }
    }
    this->parent = this->nextSbling = nullptr; // 彻底从家庭中脱离 // 当前结点不再有双亲结点以及当前结点不再有兄弟结点
    // 为什么这句代码不会将parent置空：parent是指针，this->parent是成员变量
}

LinkTree::LinkTree()
{
    // root = new TreeNode(0); // 根结点不能为空
    root = new TreeNode(nullptr);
}

LinkTree::~LinkTree()
{
    FreeNode(root);
}

void LinkTree::show()
{
    show(root, -1); // 根结点当-1层
}

DoubleLinkList LinkTree::FindByElement(const ElementType &element)
{
    DoubleLinkList lsit;
    FindNode(root, element, lsit);
    return lsit;
}

int LinkTree::GetTreeHeight()
{
    return GetNodeHeight(root) - 1;
}

int LinkTree::Size()
{
    int count = 0;
    GetNodeSize(root, count);
    return count - 1;
}

int LinkTree::leaves()
{
    int count = 0;
    GetNodeLeave(root, count);
    return count;
}

void LinkTree::GetNodeLeave(TreeNode *node, int &count)
{
    if (node == nullptr)
        return;
    if (node->firstChild == nullptr)
    {
        count++;
    }
    GetNodeLeave(node->firstChild, count);
    GetNodeLeave(node->nextSbling, count);
}

void LinkTree::GetNodeSize(TreeNode *node, int &count)
{
    if (node == nullptr)
        return;
    count++;
    GetNodeSize(node->firstChild, count);
    GetNodeSize(node->nextSbling, count);
}

int LinkTree::GetNodeHeight(TreeNode *node)
{
    if (node == nullptr)
        return 0;
    int MaxHeight = 0;
    TreeNode *treavelPoint = node->firstChild;
    while (treavelPoint != nullptr)
    {
        int NodeHeight = GetNodeHeight(treavelPoint); // 递归计算子结点高度
        MaxHeight = MaxHeight > NodeHeight ? MaxHeight : NodeHeight;
        treavelPoint = treavelPoint->nextSbling;
    }
    return MaxHeight + 1;
}

void LinkTree::FindNode(TreeNode *node, const ElementType &element, DoubleLinkList &list)
{
    if (node == nullptr)
        return;
    if (node->data == element && node != root)
        list.InsertTail(node);
    FindNode(node->firstChild, element, list); // 接着找
    FindNode(node->nextSbling, element, list);
}

void LinkTree::show(TreeNode *node, int deepth)
{
    if (node == nullptr)
        return;
    if (node->parent != nullptr) // 不是根结点才打印 (根结点默认无值)
    {
        // if (deepth > 0)
        // {
        //     // std::cout << "|";
        //     for (int i = 0; i < deepth; i++)
        //     {
        //         std::cout << "   ";
        //     }
        //     std::cout << "|__";
        // }
        std::cout << node->data << std::endl;
    }

    // 深度优先遍历
    show(node->firstChild, deepth + 1); // 打印孩子
    show(node->nextSbling, deepth);     // 打印兄弟

    // 广度优先
    // show(node->nextSbling);
    // show(node->firstChild);
}

void LinkTree::FreeNode(TreeNode *node)
{
    if (node == nullptr)
        return;
    // 它是最后释放的，先放兄弟和孩子
    FreeNode(node->firstChild);
    FreeNode(node->nextSbling);
    // std::cout << node->data << " ";
    delete node;
}
